package com.moralesce.gt.math;

import static java.math.BigInteger.ZERO;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

/**
 * In mathematics, a combination is a way of selecting several things out of a
 * larger group, where the order of those things does not matter.
 * 
 * <p>
 * In smaller cases it is possible to count the number of combinations. For
 * example given three fruit, say an apple, orange and pear, there are three
 * combinations of two that can be drawn from this set: an apple and a pear; an
 * apple and an orange; or a pear and an orange.
 * </p>
 * 
 * <p>
 * With larger cases it becomes much more difficult to enumerate all possible
 * combinations. The Combination class addresses this issue by providing the
 * capability to return all possible combinations of arbitrarily large sets.
 * </p>
 * 
 * <p>
 * Image a scenario where we have six people in a choir. The choir wants to try
 * out a new song, which requires a duet. The choir are looking for the best two
 * people in order to create that perfect sound. Produce a roster of all
 * possible duet matchups so the choir can demo and ultimatley pick the best
 * duo.
 * </p>
 * 
 * <code>
 *      // First, let's establish our choir.
 * 		String[] choir = new String[] { "Bob", "Mary", "Joe", "Suzy", "Bill", "Alice" };
 * 
 *      // We provide the combination class with all members of our choir, and how many we want to choose.
 * 		Combination<String> combination = new Combination<String>(choir, 2);
 * 		
 * 	    // The list method will return a list comprising every possible 2-person combination.
 * 		List<List<String>> duets = combination.list();
 * 
 * 		for(List<String> duet : duets) {
 * 			for(String singer : duet) {
 *              // do something...
 *          }
 * 		}
 * </code>
 * 
 * <p>
 * The combination class isn't limited to choosing primitives and strings. It
 * can be used to choose any type of object. Given a deck of 52 cards, the code
 * example below shows how one can produce every possible 5-card hand. This
 * example makes use of the Deck, Card and Hand class from this library.
 * </p>
 * 
 * <code>
 *      // Creates a list of every possible 5-card hand.
 * 		List<List<Card>> everyPossibleFiveCardHand = new Combination(new Deck().cards(), 5).list();
 * 
 *      // We iterate over the list, constructing five-card Hands. 
 * 		List<Hand> hands = new ArrayList<Hand>();
 * 		for (List<Card> cards : everyPossibleFiveCardHand) {
 * 			hands.add(Hand.newInstance(cards));
 * 		}
 * 
 * 	    // At this point, our hands list now contains all 2,598,960 5-card poker hands! We could have also done
 *      // this is were we just interested in the count.
 *      BigInteger total = new Combination(new Deck().cards()).choose(5).total();
 * </code>
 * 
 * <p>
 * Credit goes to Michael Gilleland for posting and desribing the original
 * algorithm and source code here: http://www.merriampark.com/comb.htm
 * </p>
 * 
 * @author Brandon Grenier
 */
@SuppressWarnings("unchecked")
public class Combination<T> {

	private BigInteger remaining;

	private final T[] set;
	private final Integer r;
	private final BigInteger total;

	/**
	 * Constructs a combination choosing r elements from the specified
	 * collection.
	 * 
	 * @param set The collection to choose from.
	 * @param r The number to choose.
	 */
	public Combination(Collection<T> set, Integer r) {
		this((T[]) set.toArray(), r);
	}

	/**
	 * Constructs a combination choosing r elements the specified array.
	 * 
	 * @param set The array to choose from.
	 * @param r The number to choose.
	 */
	public Combination(T[] set, Integer r) {
		if (set.length == 0) {
			throw new IllegalArgumentException("The set cannot be empty.");
		}
		if (r > set.length) {
			throw new IllegalArgumentException("Cannot choose " + r + " elements, there are only " + set.length + " elements in the collection!");
		}
		if (r < 0) {
			throw new IllegalArgumentException("Cannot choose a negative number!");
		}
		this.set = set;
		this.r = r;
		this.remaining = factorial(this.set.length).divide(factorial(this.r).multiply(factorial(this.set.length - this.r)));
		this.total = factorial(this.set.length).divide(factorial(this.r).multiply(factorial(this.set.length - this.r)));
	}

	/**
	 * Returns the total number of combinations.
	 * 
	 * This method simply calculates and returns the total number of
	 * combinations based on choosing r elements from the set, it does not
	 * enumerate through the possible combinations.
	 * 
	 * @return The total number of combinations.
	 */
	public BigInteger total() {
		return total;
	}

	/**
	 * Returns every possible combination as a result of choosing r elements
	 * from the set.
	 * 
	 * @return A List<List<T>> containing every possible combination as a result
	 * of choosing r elements.
	 */
	public List<List<T>> list() {
		if (r == 0) {
			new ArrayList<List<T>>(0);
		}

		int[] chosen = new int[r];
		for (int i = 0; i < chosen.length; i++) {
			chosen[i] = i;
		}

		List<List<T>> results = new ArrayList<List<T>>(total.intValue());
		while (!remaining.equals(ZERO)) {
			int[] indices = next(chosen);
			List<T> elements = new ArrayList<T>();
			for (int i = 0; i < indices.length; i++) {
				elements.add(set[indices[i]]);
			}
			results.add(elements);
		}
		return results;
	}

	private int[] next(int[] a) {
		if (remaining.equals(total)) {
			remaining = remaining.subtract(BigInteger.ONE);
			return a;
		}

		int i = r - 1;
		while (a[i] == set.length - r + i) {
			i--;
		}
		a[i] = a[i] + 1;
		for (int j = i + 1; j < r; j++) {
			a[j] = a[i] + j - i;
		}
		this.remaining = remaining.subtract(BigInteger.ONE);
		return a;
	}

	private BigInteger factorial(Integer number) {
		BigInteger factorial = BigInteger.ONE;
		for (int i = number; i > 1; i--) {
			factorial = factorial.multiply(new BigInteger(Integer.toString(i)));
		}
		return factorial;
	}

}
